package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=23449&ru=/ta/sql-quick-study&qru=/ta/sql-quick-study/question-ranking">链表中环的入口结点</a>
 * <p>给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。</p>
 * @author c2b
 * @since 2023/3/7 16:22
 */
public class JzOffer0023EntryNodeOfLoop {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        // 先判断是否有环。定义快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果快指针和慢指针装上了，说明有环
            if (fast == slow) {
                fast = pHead;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(2);
        head.next = head;
        //head.next = new ListNode(2);
        //head.next.next = new ListNode(3);
        //head.next.next.next = new ListNode(4);
        //head.next.next.next.next = new ListNode(5);
        //head.next.next.next.next.next = head.next.next;
        JzOffer0023EntryNodeOfLoop jzOffer0023EntryNodeOfLoop = new JzOffer0023EntryNodeOfLoop();
        ListNode listNode = jzOffer0023EntryNodeOfLoop.EntryNodeOfLoop(head);
        System.out.println(listNode);
    }
}
